package com.cuz.daileetcode.utils.heap;

import javafx.util.Pair;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Objects;

/**
 * @author cuzz
 * @version 1.0
 * @description: 自己实现的堆
 * A为什么不使用java自带的优先队列
 * 因为java的优先队列更新元素需要全部清空然后插入更新后的数据 非常低效
 * <p>
 * B什么时候使用有相对立什么时候使用这个堆
 * 1.自己实现堆适用于：需要更新堆中元素进行堆向上or向下（取决于大根堆or小根堆）的情况
 * 2.java自带的优先队列适用于：只需要简单的新增和获取堆中元素的情况
 * C代码说明
 * 1.可能存在bug
 * 2.学习ArrayList的扩容机制 搞一个玩一下
 * @date 22:49 2021/12/12
 **/
public class Heap<T> {

    /**
     * 堆是个二叉树 那么使用16 可容纳3 层满二叉树多1
     * 似乎是可减少扩容次数 当然我也不知道是不是这个道理
     * 这个要研究下 TODO
     */
    private final static int DEFAULT_HEAP_SIZE = 16;
    /**
     * 堆中元素
     */
    private Object[] elementData;
    /***
     * 空堆
     */
    private static final Object[] EMPTY_HEAP_ARRAY = {};
    /***
     * 默认大小堆 EMPTY_HEAP_ARRAY 和 DEFAULT_HEAP_ARRAY 可以区分 到底是使用0大小的堆
     * 还是使用默认大小的堆
     */
    private static final Object[] DEFAULT_HEAP_ARRAY = {};
    /**
     * 堆大小
     * <p>
     * 堆大小表示：
     * 如果元素对应的index小于等于堆大小 那么不属于堆中元素
     * 反之才是堆中元素
     *
     * @serial
     */
    private int heapSize = 0;
    /***
     * 最大堆大小，因数组中保留一些头字信息
     * 尝试分配较大的数组且如果请求的数组大小超过VM限制可能会导致OutOfMemoryError
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    /***
     * 堆元素是需要排序的，
     * 如果比较器为空 那么使用comparable自己的排序规则（如果对象没用实现 那么抛出异常）
     */
    private Comparator<T> comparator = null;

    /***
     * 私有构造方法，建议使用工厂方法
     */
    private Heap() {
    }

    /**
     * 使用默认容量大小的堆
     *
     * @return heap   其中heap.elementData = DEFAULT_HEAP_ARRAY;
     */
    public static <T> Heap<T> create() {
        Heap<T> heap = new Heap<>();
        heap.elementData = DEFAULT_HEAP_ARRAY;
        return heap;
    }

    private static <T> Heap<T> createWithZeroCapacity() {
        Heap<T> heap = new Heap<>();
        heap.elementData = EMPTY_HEAP_ARRAY;
        return heap;
    }

    public static <T> Heap<T> create(int initialCapacity) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("容量不可以小于0");
        }
        if (initialCapacity == 0) {
            //如果为0 elementData = EMPTY_HEAP_ARRAY;
            return createWithZeroCapacity();
        }
        Heap<T> heap = new Heap<>();
        heap.heapSize = initialCapacity;
        heap.elementData = DEFAULT_HEAP_ARRAY;
        return heap;
    }

    public static <T> Heap<T> create(Comparator<T> comparator) {
        Heap<T> heap = create();
        heap.comparator = Objects.requireNonNull(comparator);
        return heap;
    }

    public static <T> Heap<T> create(int initialCapacity, Comparator<T> comparator) {
        Heap<T> heap = create(initialCapacity);
        heap.comparator = Objects.requireNonNull(comparator);
        return heap;
    }

    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        // 容量小于 64时新容量为两倍加2 ，反之增加50%
        //优先队列这样做，why todo
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                (oldCapacity + 2) :
                (oldCapacity >> 1));
        //发生了溢出 说明源容量很大 不可以分配1.5倍了
        if (newCapacity > MAX_ARRAY_SIZE) {
            newCapacity = hugeCapacity(minCapacity);
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) {
            throw new OutOfMemoryError();
        }
        //尽力扩容
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }


    public void add(T element) {
        Objects.requireNonNull(element);
        ensureCapacityInternal(elementData.length + 1);
        //堆为空
        if (heapSize == 0) {
            elementData[heapSize] = element;
        } else {
            tuneUp(heapSize,element);
        }
        heapSize++;
    }




    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private void ensureExplicitCapacity(int minCapacity) {
        //如果最小的大于当前堆数组大小 扩容
        if (minCapacity - elementData.length > 0) {
            grow(minCapacity);
        }
    }

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        //如果是默认堆 使用默认堆大小 和目前容量的较大者
        if (elementData == DEFAULT_HEAP_ARRAY) {
            return Math.max(DEFAULT_HEAP_SIZE, minCapacity);
        }
        return minCapacity;
    }

    /**
     * 调整堆
     *
     * @param index   需要调整的位置
     * @param element 需要插入的元素
     */
    private void tuneUp(int index, T element) {
        if (comparator != null) {
            tuneUpByComparator(index, element);
        } else if (element instanceof Comparator) {
            tuneUpComparable(index, element);
        }
        throw new ClassCastException("插入元素无法比较");
    }

    private void tuneUpByComparator(int index, T element) {
        while (index > 0) {
            //父节点位置为当前节点位置（减1）/2
            int fatherIndex = (index - 1) >> 1;
            T fatherNode = (T) elementData[fatherIndex];
            //比较其两个参数的顺序。当第一个参数小于、，返回负整数、等于返回0，大于返回正整数
            //当前节点大于那么 结束
            if (comparator.compare(element, fatherNode) >= 0) {
                break;
            }
            //把父节点的数据复制到当前位置
            elementData[index] = fatherNode;
            //当前位置更新为父节点位置
            index = fatherIndex;
        }
        //最后找到这个元素应该位于的位置
        elementData[index] = element;
    }

    private void tuneUpComparable(int index, T element) {
        Comparable<? super T> newNode = (Comparable<? super T>) element;
        while (index > 0) {
            //父节点位置为当前节点位置（减1）/2
            int fatherIndex = (index - 1) >> 1;
            T fatherNode = (T) elementData[fatherIndex];
            //比较其两个参数的顺序。当第一个参数小于、，返回负整数、等于返回0，大于返回正整数
            //当前节点大于那么 结束
            if (newNode.compareTo(fatherNode) >= 0) {
                break;
            }
            //把父节点的数据复制到当前位置
            elementData[index] = fatherNode;
            //当前位置更新为父节点位置
            index = fatherIndex;
        }
        //最后找到这个元素应该位于的位置
        elementData[index] = element;
    }


}
